package hot_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum_15 {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3) return list;
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int mid = i + 1;
            int end = nums.length - 1;
            while (end > mid) {
                int tmp = nums[i] + nums[mid] + nums[end];
                if (tmp == 0) {
                    list.add(Arrays.asList(nums[i], nums[mid], nums[end]));
                    while (mid < end && nums[mid] == nums[mid + 1]) {
                        mid++;
                    }
                    while (mid < end && nums[end] == nums[end - 1]) {
                        end--;
                    }
                    mid++;end--;
                }
                //以下代码不能过滤掉相同的值，如果过滤了就会导致-2，1，1这样的被过滤，没结果
                else if (tmp > 0) end--;
                else if (tmp < 0) mid++;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] nums = {-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        //int[] nums = { -2,0,0,0,1,1};
        List list = threeSum(nums);
        System.out.println(list);
    }
}
